A Slice of Pi

Nota

Este é um problema razoavelmente complicado! Como tal, será importante fazer um plano antes de começar a escrever qualquer código. Você pode querer ler a seção sobre estratégia, que fornece algumas dicas para gerenciar a complexidade desse problema, antes de começar (mas depois de ler a descrição do problema).

1) Descrição do Problema

Neste problema, consideraremos um método interessante para aproximar o valor de $\pi$.

Imagine que você não soubesse o valor de $\pi$, mas conhecesse a relação entre a área de um círculo e $\pi$, especificamente que: $$A =\pi r^2$$

Poderíamos então usar a equação de área e o método a seguir para aproximar $\pi$ computacionalmente. Em primeiro lugar, considere um círculo inscrito em um quadrado:

Tente agora:

Qual fração da área do quadrado ($A_q$) é ocupada pelo círculo ($A_c$), em termos de $\pi$ e do raio do círculo $r$?

Mostrar/Esconder $$A_q = (2r)^2 = 4r^2$$ $$A_c = \pi r^2$$ $$\frac{A_c}{A_q} = \frac{\pi}{4}$$

Medir essa proporção nos daria um caminho claro para calcular $\pi$ com base na fórmula acima (podemos apenas reorganizar a fórmula para encontrar $\pi$). Mas acontece que a proporção em si é difícil de medir. No entanto, podemos pensar em uma maneira de aproximar isso.

Para aproximar essa proporção, podemos primeiro cortar o quadrado em uma grade com base em um parâmetro de discretização de valor ímpar $p_d$, que nos diz quantas "células de grade" deve haver ao longo de cada eixo. Abaixo está o mesmo desenho sobreposto com uma grade correspondente a $p_d = 5$:

Nesta visão, se rotularmos o centro da célula do meio como $(0,0)$ e assumirmos que cada célula tem comprimento unitário, então podemos rotular cada célula com uma localização $(x, y)$:

Quadrados cujo centro está dentro ou exatamente na borda do círculo podem ser contados testando se, para cada célula (x, y), a distância do centro do círculo ao centro dessa célula é menor que o raio: $$\sqrt{x^2 + y^2} \le \frac{p_d}{2}$$

Tente agora:

Por que a distância é comparada com $p_d/2$?

Mostrar/Esconder O raio do círculo é exatamente a metade da largura da caixa. Como a largura da caixa (em unidades de "célula de grade") é $p_d$, isso significa que o raio do círculo é $p_d/2$.

O número de células que satisfazem essa condição dividido pelo número total de células na grade se aproxima da proporção $A_c/A_q$, que, como vimos acima, podemos usar para aproximar $\pi$. Conforme $p_d$ muda, a razão (em termos de número de células da grade) se aproxima da razão teórica, e assim nossa estimativa de $\pi$ se aproxima do valor verdadeiro de $\pi$ também!

Nos desenhos abaixo, os quadrados que satisfazem esta condição são coloridos em vermelho, para $p_d=5$, $p_d=13$, $p_d=101$, e algumas estatísticas são mostradas para cada caso (que você pode usar para ajudar a testar seu código enquanto trabalha!).

Como você pode ver, conforme $p_d$ aumenta, a região sombreada parece ficar cada vez mais perto da área real do círculo, e nossa estimativa fica cada vez mais perto de $\pi$! (demora um pouco para obter uma aproximação de $\pi$, talvez próximo a $p_d \to 5000$).

Tente agora:

Que valor este método produziria quando $p_d=1$?

Mostrar/Esconder Neste caso, existe apenas uma célula! E seu centro está dentro do círculo, então nossa estimativa é (1 célula interna / 1 célula total) * 4 = 4, o que, na verdade, não é uma estimativa tão ruim!

2) Especificação do Programa

Escreva um programa que estime $\pi$ usando o método acima para um valor particular de $p_d$ que não seja um dos três valores acima e então atribua esse valor a uma variável out. A primeira linha em seu programa deve definir uma variável p_d (com o underscore!) para conter o valor de $p_d$ a se usar. Por exemplo:

p_d = 10

e deve atribuir a out a estimativa de $\pi$ obtida pelo método acima e seu valor de $p_d$. Não arredonde nenhum valor!

3) Estratégia e Design

Este é um problema bastante complicado e, portanto, é uma ótima oportunidade para falar um pouco sobre o design de programas. Frequentemente, podemos pensar em como gerenciar a complexidade de um programa dividindo o programa em etapas para ajudar a tornar o processo um pouco mais gerenciável. Às vezes, é mais fácil no longo prazo começar não escrevendo o problema que realmente queremos resolver, mas sim um problema semelhante e menor que nos ajuda a realizar uma das etapas que estamos interessados em resolver.

Neste problema, há várias coisas que temos que fazer:

  1. temos que considerar cada célula da grade
  2. temos que calcular as distâncias entre as células da grade e a célula central
  3. temos que usar esse resultado para verificar se a célula em questão está dentro do círculo
  4. temos que acompanhar quantas células estão no círculo e quantas estão no quadrado

Isso é bastante, mas algumas dessas peças podem ser abordadas por meio de uma abordagem iterativa para resolver esse problema. Uma dessas estratégias é descrita abaixo (que você pode seguir, ou não, conforme achar adequado!). Ao longo do caminho, a seção de leituras desta tarefa sobre debugging pode ser útil!

  • Pode fazer sentido começar com um programa que usa p_d para simplesmente imprimir os pares $(x,y)$ de todas as células que queremos verificar. Você pode testar isso com p_d = 5 para ter certeza de obter todas as mesmas coordenadas do diagrama acima.
    • Mesmo este não é necessariamente um problema fácil! Você pode querer quebrar isso em partes e começar escrevendo um programa que use p_d para imprimir apenas os valores $x$ das células que queremos verificar. Depois de ter isso, como você pode expandir essa ideia para imprimir os pares $(x,y)$?
  • Assim que tiver isso funcionando, você pode modificar seu programa para que ele imprima não apenas o par $(x,y)$ associado a esse ponto, mas também a distância do centro a esse ponto (que você pode verificar por mão para cada célula – use simetria para reduzir o trabalho quando estiver fazendo a mão!).
  • Em seguida, você pode adicionar a verificação se o centro da célula está dentro do círculo ou não e imprimir esse resultado (True ou False) em vez de imprimir a distância diretamente. Novamente, você pode verificar esta etapa certificando-se de que todas as células vermelhas no diagrama p_d = 5 acima imprimem True em seu código quando p_d = 5.
  • Em seguida, você pode modificar seu código para controlar o número de células dentro e fora do círculo e para imprimir esses valores uma vez que seja feito considerando todas as células. Novamente, você pode compará-los com os desenhos acima para vários valores de p_d mostrados acima.
  • Finalmente, você pode remover todas as instruções print úteis que você usou para debugging e certificar-se de que seu programa apenas atribua o valor pedido a out.

Submissão

Quando estiver pronto (depois de ter simulado manualmente e testado em sua própria máquina e estiver convencido de que seu programa fará a coisa certa), faça upload do seu arquivo Python no Problema 1.6 no Gradescope. Lembre de nomear seu arquivo p1_6.py.